// GIS综合算法
#include "./model/gis-model.h"

/// @brief 计算三角形面积
/// @param p1 第一个点指针
/// @param p2 第二个点指针
/// @param p3 第三个点指针
/// @return 三角形面积
double triangleSquare(Point *p1, Point *p2, Point *p3)
{
	// 计算公式：向量p1p3与p1p2的叉乘的二分之一再取绝对值即可
	Vector *v1 = createVectorByTwoPoint(p1, p3);
	Vector *v2 = createVectorByTwoPoint(p1, p2);
	return fabs(vectorCrossProduct(v1, v2) / 2);
}

/// @brief 计算多边形面积
/// @param polygon 多边形对象指针
/// @return 多边形的面积
double polygonSquare(Polygon *polygon)
{
	// 多边形面积计算很简单，比如说多边形有n个顶点，则将其拆分成n - 2三角形算就行
	double total = 0;
	int i;
	for (i = 1; i < polygon->pointCount - 1; i++)
	{
		// 总是由第0个、第i个和第i - 1个点组成三角形
		total += triangleSquare(&polygon->points[0], &polygon->points[i], &polygon->points[i + 1]);
	}
	return total;
}

/// @brief 判断点和线段所在的直线的关系，将从控制台输出点是在线段上还是左边/右边
/// @param point 点对象指针
/// @param line 线段对象指针
void pointAndLine(Point *point, Line *line)
{
	// 例如有线段AB和点P，则判断向量AP与AB的叉乘，若两者叉乘为0说明点P位于AB线段所在的直线上，小于0则在线段左边，大于0则在线段右边
	Point *a = createPoint(line->startX, line->startY);
	Point *b = createPoint(line->endX, line->endY);
	Vector *v1 = createVectorByTwoPoint(a, point);
	Vector *v2 = createVectorByTwoPoint(a, b);
	double result = vectorCrossProduct(v1, v2);
	if (result == 0)
	{
		printf("点在线段所在直线上！\n");
	}
	else if (result < 0)
	{
		printf("点在线段的左边！\n");
	}
	else
	{
		printf("点在线段的右边！\n");
	}
}

/// @brief 判断点是否在线段上（在线段所在直线上不算）
/// @param point 点指针
/// @param line 线段指针
/// @return 点是否在线段上
int pointOnLine(Point *point, Line *line)
{
	// 假设线段AB和P，则创建向量AP与AB并叉乘，不为0说明点不可能在线段上，为0则比较线段两端坐标和点坐标
	Point *a = createPoint(line->startX, line->startY);
	Point *b = createPoint(line->endX, line->endY);
	Vector *ap = createVectorByTwoPoint(a, point);
	Vector *ab = createVectorByTwoPoint(a, b);
	double result = vectorCrossProduct(ap, ab);
	if (result != 0)
	{
		return 0;
	}
	// 点x坐标需要在线段两端的x之间，y坐标同理
	if (((point->x >= line->startX && point->x <= line->endX) || (point->x >= line->endX && point->x <= line->startX)) && (point->y >= line->startY && point->y <= line->endY) || (point->y >= line->endY && point->y <= line->startY))
	{
		return 1;
	}
	return 0;
}

/// @brief 取两者最大值
/// @param d1 第一个数
/// @param d2 第二个数
/// @return 最大值
double max(double d1, double d2)
{
	return d1 > d2 ? d1 : d2;
}

/// @brief 取两者最小值
/// @param d1 第一个数
/// @param d2 第二个数
/// @return 最小值
double min(double d1, double d2)
{
	return d1 < d2 ? d1 : d2;
}

/// @brief 两线段是否相交
/// @param line1 线段1指针
/// @param line2 线段2指针
/// @return 两线段是否相交
int twoLinePosition(Line *line1, Line *line2)
{
	// 第一步：快速排斥，判断两线段在x轴和y轴投影是否有重合，若没有说明不可能相交，否则进行第二步
	if (max(line1->startX, line1->endX) < min(line2->startX, line2->endX) ||
		max(line2->startX, line2->endX) < min(line1->startX, line1->endX) ||
		max(line1->startY, line1->endY) < min(line2->startY, line2->endY) ||
		max(line2->startY, line2->endY) < min(line1->startY, line1->endY))
	{
		return 0;
	}
	// 第二步：判断一个线段两端点是否在另一线段两侧，比如AB和CD，判断向量叉乘CA×CD与CB×CD是否异号，若异号则说明两线段相交，为0说明一个线段有一个端点刚好在另一个线段上，也算是相交
	Point *a = createPoint(line1->startX, line1->startY);
	Point *b = createPoint(line1->endX, line1->endY);
	Point *c = createPoint(line2->startX, line2->startY);
	Vector *ca = createVectorByTwoPoint(c, a);
	Vector *cb = createVectorByTwoPoint(c, b);
	Vector *cd = createVectorByLine(line2);
	return vectorCrossProduct(ca, cd) * vectorCrossProduct(cb, cd) <= 0;
}

/// @brief 判断点和多边形位置（转角法）
/// @param point 点对象指针
/// @param polygon 多边形对象指针
/// @return 点是否在多边形内
int pointAndPolygonAngle(Point *point, Polygon *polygon)
{
	// 分别表示总角度和，当前两个向量角度
	double total = 0, currentAngle;
	// 计算转角夹角的两个向量
	Vector *v1, *v2;
	// 遍历下标
	int i;
	for (i = 0; i < polygon->pointCount; i++)
	{
		// v1表示判断点到当前遍历点向量
		v1 = createVectorByTwoPoint(point, &polygon->points[i]);
		// v2表示判断点到当前遍历的下一个点向量，若当前为左后一个点，则v2为判断点到多边形第一个点向量
		if (i == polygon->pointCount - 1)
		{
			v2 = createVectorByTwoPoint(point, &polygon->points[0]);
		}
		else
		{
			v2 = createVectorByTwoPoint(point, &polygon->points[i + 1]);
		}
		// 求角度
		currentAngle = vectorAngle(v1, v2);
		// 判断v1到v2是顺时针还是逆时针，顺时针赋值角度为正
		if (vectorCrossProduct(v1, v2) > 0)
		{
			currentAngle = -currentAngle;
		}
		total += currentAngle;
	}
	// 取绝对值（四舍五入）
	int totalArc = (int)(fabs(total) + 0.5);
	// 一般来说，当点在多边形内时转角和为360°，但是凹多边形可能出现大于360°但是是360°的倍数的情况
	return totalArc / 360 >= 1;
}

/// @brief 判断点是否在简单多边形内（射线法）
/// @param point 点指针
/// @param polygon 多边形指针
/// @return 点是否在多边形内
int pointAndPolygonRay(Point *point, Polygon *polygon)
{
	// 从点向x正方向作射线，依次考虑以下特殊情况：
	// 1. 射线与多边形某边平行且该边两个点y坐标与点的y坐标相等
	// 2. 点在多边形的顶点上
	// 3. 点在多边形某条边上
	// 遇到上述特殊情况直接return 0
	// 射线穿过边的判定条件：点的y坐标在某边的两点的y坐标之间且该点在直线下侧
	// 射线与多边形每条边交点个数若为奇数说明在多边形内，偶数则说明在多边形外
	int i, crossCount = 0;
	Line *edge;
	for (i = 0; i < polygon->pointCount; i++)
	{
		// 创建边
		if (i == polygon->pointCount - 1)
		{
			edge = createLine(polygon->points[i].x, polygon->points[i].y, polygon->points[0].x, polygon->points[0].y);
		}
		else
		{
			edge = createLine(polygon->points[i].x, polygon->points[i].y, polygon->points[i + 1].x, polygon->points[i + 1].y);
		}
		// 是否平行且y坐标相等
		if (edge->startY == edge->endY)
		{
			if (point->y == edge->startY)
			{
				return 0;
			}
			// 平行但是y坐标不相等，则一定不相交，跳过到下一次
			continue;
		}
		// 点是否和多边形顶点重合
		if (point->x == polygon->points[i].x && point->y == polygon->points[i].y)
		{
			return 0;
		}
		// 点是否在多边形当前边上
		if (pointOnLine(point, edge))
		{
			return 0;
		}
		// 然后判断相交
		// 条件1：点的y坐标在两者之间
		int c1 = (point->y >= edge->startY && point->y <= edge->endY) || (point->y >= edge->endY && point->y <= edge->startY);
		// 条件2：点位于线段所在直线下方（左边）
		// 先判断边是否垂直，垂直的话需要点在边左边
		// 不垂直则构建直线方程：
		// 用edge两个点构建直线方程：Y - edge->startY = k * (X - edge->startX)
		// 其中，k = (edge->endY - edge->startY) / (edge->endX - edge->startX)
		// 所以，直线方程为：Y = ((edge->endY - edge->startY) / (edge->endX - edge->startX)) * (X - edge->startX) + edge->startY
		// 把point->x带入X，若得到Y大于point->y则说明点在直线下方
		int c2;
		// 先判断垂直
		if (edge->startX == edge->endX)
		{
			c2 = point->x < edge->startX;
		}
		else
		{
			// 否则求直线方程
			// 斜率
			double k = (edge->endY - edge->startY) / (edge->endX - edge->startX);
			// 方程的值，带入点x坐标
			double yValue = k * (point->x - edge->startX) + edge->startY;
			int c2 = yValue > point->y;
		}
		if (c1 && c2)
		{
			crossCount++;
		}
	}
	return crossCount % 2 != 0;
}

/// @brief 求三角形重心
/// @param p1 三角形第一个点
/// @param p2 三角形第二个点
/// @param p3 三角形第三个点
/// @return 三角形重心
Point *triangleCenter(Point *p1, Point *p2, Point *p3)
{
	double x, y;
	x = (p1->x + p2->x + p3->x) / 3;
	y = (p1->y + p2->y + p3->y) / 3;
	Point *p = createPoint(x, y);
	return p;
}

/// @brief 求任意多边形中心
/// @param polygon 多边形对象
/// @return 多边形的中心
Point *polygonCenter(Polygon *polygon)
{
	// 求任意多边形中心，只需将多边形分解为多个三角形，依次求出每个三角形的重心，然后加权求值，权即为每个三角形面积
	// 分别表示每个三角形面积、总面积、总的带权重心坐标
	double eachArea, totalArea, totalX, totalY;
	// 每个带权重心坐标
	Point *eachCenter;
	int i;
	for (i = 1; i < polygon->pointCount - 1; i++)
	{
		eachArea = triangleSquare(&polygon->points[i - 1], &polygon->points[i], &polygon->points[i + 1]);
		eachCenter = triangleCenter(&polygon->points[i - 1], &polygon->points[i], &polygon->points[i + 1]);
		totalArea += eachArea;
		totalX += eachCenter->x * eachArea;
		totalY += eachCenter->y * eachArea;
	}
	Point *p = createPoint(totalX / totalArea, totalY / totalArea);
	return p;
}

/// @brief 判断圆和矩形是否有重叠的部分
/// @param circle 圆
/// @param rectangle 矩形
/// @return 圆和矩形是否重叠
int circleAndRectangle(Circle *circle, Rectangle *rectangle)
{
	// 第一种情况：圆心在矩形内，这样一定是重叠的
	if (circle->center->x >= rectangle->upLeft->x && circle->center->x <= rectangle->bottomRight->x && circle->center->y >= rectangle->bottomRight->y && circle->center->y <= rectangle->upLeft->y)
	{
		return 1;
	}
	// 第二种情况：圆不在矩形内
	// 又分为四种情况：圆在矩形的上下左右侧，通过计算圆心与四条边的最短距离判定
	// 圆心与边的最短距离即为：当圆心的投影在边上时则为圆心到边的垂距，否则就是圆心到距离边最近的端点的距离
	double distance, x, y;
	// 当圆在上下侧时
	if (circle->center->y > rectangle->upLeft->y || circle->center->y < rectangle->bottomRight->y)
	{
		y = circle->center->y > rectangle->upLeft->y ? rectangle->upLeft->y : rectangle->bottomRight->y;
		// 判断圆心在x轴投影是否在上/下侧边的投影内
		if (circle->center->x < rectangle->upLeft->x)
		{
			x = rectangle->upLeft->x;
		}
		else if (circle->center->x > rectangle->bottomRight->x)
		{
			x = rectangle->bottomRight->x;
		}
		else
		{
			x = circle->center->x;
		}
	}
	else
	{
		// 否则就是在圆的左右侧
		x = circle->center->x < rectangle->upLeft->x ? rectangle->upLeft->x : rectangle->bottomRight->x;
		// 判断圆心在y轴投影是否在矩形左/右侧边的投影内
		if (circle->center->y > rectangle->upLeft->y)
		{
			y = rectangle->upLeft->y;
		}
		else if (circle->center->y < rectangle->bottomRight->y)
		{
			y = rectangle->bottomRight->y;
		}
		else
		{
			y = circle->center->y;
		}
	}
	// 方便起见计算距离平方即可，与圆的半径平方做比较
	distance = pow(circle->center->x - x, 2) + pow(circle->center->y - y, 2);
	return distance <= pow(circle->radius, 2);
}

int main()
{
	Circle *c = createCircle(4, 3, 2);
	Rectangle *r = createRectangle(0, 2, 3, 0);
	printf("%d\n", circleAndRectangle(c, r));
	return 0;
}